Python算法分享系列 -- 二叉树

最近比较懒，一直没有更新，耐不住迷妹们在后台频繁的鼓励，今天我们来蹭个热点，了解下二叉树。 最近最火的一个新闻莫过于某著名程序员面试Google被拒，原因是不会反转二叉树。
今天我们就来学习二叉树。

什么是二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树常被用于实现二叉查找树和二叉堆。

如何定义一个二叉树

根据定义，我们知道二叉树最重要的是根节点，左节点和右节点，我们来实现一个类来代表二叉树：

class BinaryTree(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

实现二叉查找树（Binary Search Tree）

首先， 二叉查找树，又称二叉排序树（Binary Sort Tree）， 二叉搜索树，
它有如下特点：
（0）它是一颗空树，如果不是，它一定符合下列性质：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

先看一个二叉查找树的例子：

下面来实现它：

class BST:
    def insert_tree(self, root, value):
        if root.val > value:
            if not root.left:
                root.left = Node(value)
            else:
                self.insert_tree(root.left, value)

        if root.val < value:
            if not root.right:
                root.right = Node(value)
            else:
                self.insert_tree(root.right, value)

那么，二叉树如何实现查找呢？根据二叉树的特点，我们知道：
1.如果要查找的值等于根节点的值，成功退出。
2.如果要查找的值小于根节点的值， 递归查找左分支树， 否则，递归查找右分支树，
3.如果发现等同于要查找的值，成功退出。
4.如果子树为空，返回空。

在查找之前，我们先看看如何遍历二叉树：

   #先访问根节点，再遍历左子树，最后遍历右子树；
#并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。
   def preorder(self, root):
       if not root:
           return []
       result = [root.val]
       left_result = self.preorder(root.left)
       right_result = self.preorder(root.right)
       return result + left_result + right_result

   #中序遍历：先遍历左子树、然后访问根节点，最后遍历右子树；
#并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。
   def midorder(self, root):
       if not root:
           return []
       left_result = self.midorder(root.left)
       result = [root.val]
       right_result = self.midorder(root.right)
       return left_result + result + right_result

   #后续遍历：先遍历左子树，然后遍历右子树，最后访问根节点；
#同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。
   def postorder(self, root):
       if not root:
           return []
       left_result = self.postorder(root.left)
       right_result = self.postorder(root.right)
       result = [root.val]
       return left_result  + right_result + result

查找：

def search_node(self, root, value):
    if value in self.postorder(root):
        return True

最后，我们来看下大神回答不出来的那个问题， 交换二叉树的左右节点。

def switch_node(self, root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    self.switch_node(root.left)
    self.switch_node(root.right)
    return self.preorder(root)

由此可以看出， 二叉树的操作，最多的用到的是递归,递归的本质是自己调用自己，下面给一个函数来理解：

#求阶乘
    def factorial(n):
        if n<=1:
            return 1
        else:
            return n*factorial(n-1)
		
如何理解呢？
n = 5;    
x = factorial (n);
    x = factorial (5);                         # first call to function
    x = (5 * factorial (4));                   # recursion starts, until logic requirement satisfied
    x = (5 * (4 * factorial (3)));
    x = (5 * (4 * (3 * factorial (2))));
    x = (5 * (4 * (3 * (2 * factorial (1)))));
    x = (5 * (4 * (3 * (2 * (1)))));           # all calls made, logic ceases the recursion
    x = (5 * (4 * (3 * (2 * 1))));             # returns start as resolutions/calculations begin
    x = (5 * (4 * (3 * 2)));
    x = (5 * (4 * 6));
    x = (5 * 24);
    x = (120);                                 # final resolution/calculation before return
    x = 120;

递归的理解不尽相同， 不过读者大可不必去关心函数如何一层层调用的，因为

Recursion is the process of solving a problem in terms of smaller versions of the same problem. Since the problem gets smaller each time, the process eventually terminates in a problem (the “base case”) that can be solved directly. Be sure of three things:

• The problem gets smaller each time.
• You include a solution for the base case.
• Each case is handled correctly.

That’s really all there is to it.
参考资料：
！递归理解1
！递归理解2